package P169;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @Author DJ同学
 * @Date 2021/2/17 14:54
 * @Version 1.0
 * @Name 多数元素
 * @Problem https://leetcode-cn.com/problems/majority-element/
 * @Idea 摩尔投票
 * 每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。
 */
public class Solution2 {
    public int majorityElement(int[] nums) {
        int card_num=nums[0];
        int cnt=0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==card_num){
                cnt++;
                continue;
            }
            if(cnt==0){
                card_num=nums[i];
                cnt=1;
                continue;
            }
            cnt--;
        }
        return card_num;
    }
}
